COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\|\\M0BASL30\M1FIX25\M2BASB30\M3BASI30\M4CRTURZ\
C00003 00003	Exercising the FOR Statement
C00007 00004	Using Strings and an occasional Array
C00016 00005	\F2CS 105 solutions to problem set 2
C00021 00006	\F2CS 105 
C00026 00007	\F1CS 105 
C00030 ENDMK
C⊗;
\|\\M0BASL30;\M1FIX25;\M2BASB30;\M3BASI30;\M4CRTURZ;\;
Exercising the FOR Statement

A set of problems is presented here to help test your understanding of
FOR, READ, READON, WRITE, WRITEON, variables, and expressions.  Solutions
do not need to be handed in; the problems are provided as an aid which you
may use in any way you wish.  A solution sheet will be handed out at the
next class.

For the first six problems below your mission, if you accept it, is to
fill in the comment at the begginning of the program or write out exactly
what the program would print as its output.  (Or find mistakes).

(1)
BEGIN
COMMENT							;
INTEGER X;
FOR I:=1 UNTIL 3 DO
	BEGIN
	X:=I;
	WRITE("X",X)
	END
END.


(2)
BEGIN
COMMENT							;
FOR I:=1 UNTIL 3 DO
	FOR J:=1 UNTIL 3 DO
		WRITE(I,J)
END.


(3)
BEGIN
COMMENT							;
INTEGER SIZE;
READ(SIZE);
WRITE(" ");
FOR I:=1 UNTIL SIZE DO
	WRITEON("*");
FOR I:=1 UNTIL (SIZE-2) DO
	BEGIN
	WRITE("*");
	FOR J:=1 UNTIL (SIZE-2) DO
		WRITEON(" ");
	WRITEON("*")
	END;
WRITE("*");
FOR I:=1 UNTIL (SIZE-1) DO
	WRITEON("*")
END.

(data on next page)


This program is run once with the following data card (after the %DATA card):
4
and then run again with this card:
0


(4)
BEGIN
COMMENT							;
FOR I:=1 UNTIL 5 DO
	BEGIN
	WRITE(" ");
	FOR J:=1 UNTIL 5 DO
		WRITEON(I+J)
	END
END.


(5)
BEGIN
COMMENT							;
WRITE(" ");
FOR I:=1 UNTIL 10 DO
	WRITEON("*");
FOR I:=1 UNTIL 8 DO
	BEGIN
	WRITE(" ");
	FOR J:=1 UNTIL (9-I) DO
		WRITEON(" ");
	WRITEON("*")
	END;
WRITE(" ");
FOR I:=1 UNTIL 10 DO
	WRITEON("*")
END.


(6)
BEGIN
COMMENT							;
INTEGER X,STOP;
READ(STOP);
FOR I:=1 UNTIL STOP DO
	BEGIN
	READON(X);
	WRITE(" ");
	FOR J:=1 UNTIL X DO
		WRITEON(X)
	END
END.

This program is run with the following data card:
4  5  1  9  3


And here are two program writing problems to try.  Good luck!

(1)
Write a program which will read in 5 integers from a data card
for each integer print one line with that (i.e. the integer)
number of asterisks.


(2)
Write a program that will print out a 9 by 9 multiplication table.
A 2 by 2 multiplication table would look like this:

	1	2
1	1	2
2	2	4
Using Strings and an occasional Array

And here's another set of problems for all of you who thirst so eagerly
for knowledge.  Most of them are about strings although there are some
arrays.  The later problems build upon the earlier ones in many cases.
These programs can be run on the computer to get the answers.


(1)
Suppose we have an 8 by 8 array that has been declared as follows:
INTEGER ARRAY CHECKERBOARD(1::8,1::8);
This array then has 64 boxes in it.  Let us further suppose that each of
these boxes has either a 0,1,2,3, or 4 stored in it; where 0 stands for an
empty checkerboard square, 1 for a square with a black king, 2 for a
square with a black soldier, 3 for a red king, and 4 for a red soldier.
The box CHECKERBOARD(1,1) contains the value for the square in the upper
left hand corner of the board while CHECKERBOARD(8,8) is for the lower
right hand corner.
Consider the following procedure:

PROCEDURE PIECES_ON_ROW(INTEGER VALUE ROW);
	BEGIN
	COMMENT THE PARAMETER ROW IS AN INTEGER BETWEEN 1 AND 8 WHICH SPECIFIES
	  A ROW ON THE CHECKERBOARD.  THIS PROCEDURE THEN COUNTS THE NUMBER OF
	  PIECES ON THAT ROW AND PRINTS THE RESULT.;
	INTEGER COUNT;
	COUNT:=0;
	FOR I:=1 UNTIL 8 DO
		IF CHECKERBOARD(ROW,I)>0 THEN COUNT:=COUNT+1;
	WRITE(COUNT," PIECES ON ROW ",ROW)
	END;

As this procedure is written, the computer will quit in disgust if the
procedure is called with an actual parameter that has a value greater than
8 or less than 1.  Your job is to rewrite the procedure so that it will
simply print an error message and then end normally in such a case.  Also,
write similar procedures for printing out a) the number of red kings in
any particular column of the checkerboard, and b) the number of black
pieces on the diagonal from square (1,1) to square (8,8), i.e. the
diagonal from the upper left hand corner to the lower right hand corner.


(2)
PROCEDURE PRINT_NO_BLANK(STRING(80) VALUE TEXT);
	BEGIN
	COMMENT				;
	WRITE(" ");
	FOR POINTER:=0 UNTIL 79 DO
		IF TEXT(POINTER|1)¬=" " THEN WRITEON(TEXT(POINTER|1))
	END;

Your mission is to study this procedure until you understand what it does,
then fill in the comment describing what this procedure
does and give the printed results for the following two procedure calls:

PRINT_NO_BLANK("  THIS     IS      FULL        OF             HOLES.");
PRINT_NO_BLANK("BENJAMIN FRANKLIN WORE     GREEN       UNDERWEAR.");


(3)
STRING(1) PROCEDURE NEXT_LETTER(STRING(80) VALUE TEXT,INTEGER VALUE RESULT POS);
	BEGIN
	COMMENT THIS PROCEDURE STARTS AT POSITION POS IN THE STRING TEXT AND
	  RETURNS THE NEXT ALPHABETIC LETTER IN TEXT.;
	STRING(1) ANSWER;
	ANSWER:=" ";
	WHILE (POS<=79) AND (ANSWER=" ") DO
		IF (TEXT(POS|1)>="A") AND (TEXT(POS|1)<="Z") THEN
			ANSWER:=TEXT(POS|1)
		ELSE POS:=POS+1;
	ANSWER
	END;

Note that the above procedure is typed and will return a value.  Also note
that the parameter POS is a RESULT parameter.  Study the procedure and
understand what it does, then answer the following:

a) what happens if there are no letters in TEXT?
b) what happens if POS is 100?
c) what happens if POS is -4?
d) if in b) or c) you thought the computer would quit in disgust, outline
   a change so that the procedure would not blow up
e) suppose the following statements came after the procedure in the main
   program.  What would they print out? (The comment helps number the
   positions in the string.)

INTEGER CHARPOS;
CHARPOS:=0;
WRITE(NEXT_LETTER("THERE ARE 100 MARMOTS HERE.",CHARPOS));
COMMENT	           0    5    1    1    2
		  	     0    5    0      ;
CHARPOS:=5;
WRITE(NEXT_LETTER("THERE ARE 100 MARMOTS HERE.",CHARPOS));
WRITE(CHARPOS);
CHARPOS:=10;
WRITE(NEXT_LETTER("THERE ARE 100 MARMOTS HERE.",CHARPOS));
WRITE(CHARPOS);
WRITE(NEXT_LETTER("9999999999999999999999999999999999",CHARPOS));


(4)
What does this program do (in English)?  Assume the program knows about
the procedure in (3).  How could the program below be simplified if
NEXT_LETTER added one to POS so that POS always pointed to the character
right after the one returned as the answer?  Why does the WHILE loop work
properly?
	
BEGIN
COMMENT				;
INTEGER COUNT, CHARPOS;
STRING(80) TEXT;
READ(TEXT); 
COUNT:=0;  CHARPOS:=0;
WHILE NEXT_LETTER(TEXT,CHARPOS)¬=" " DO
	BEGIN
	COUNT:=COUNT+1;
	CHARPOS:=CHARPOS+1
	END;
WRITE(COUNT," LETTERS IN TEXT.")
END.



(5)
Write a program which reads in a string (less than 80 characters long)
and prints the substring of this string that is between the first "<" 
and the first ">".  For example, if the input is "FOR <ITERATION VARIABLE>:=
1 UNTIL 5 DO", the program should print out: INTERATION VARIABLE.
The program has a number of possible errors that it may consider
checking for.  

Once this program has been written, energetic people
can try to write a procedure NEXT_WORD which uses ideas in this program
and in NEXT_LETTER.  Assume a word is a continuous group of letters.
Instead of taking all characters between the "<" and the ">", you will
want to take all letters between two characters that are not letters.
A NEXT_WORD procedure would be very useful in going through a sentence
word by word.\.
\F2CS 105 solutions to problem set 2
30 April 1976


\F0\JHere's the solutions to the problems of problem set 2.  They are mostly
uncommented in order to save paper.\.


\F2(1)
\F1PROCEDURE PIECES_ON_ROW(INTEGER VALUE ROW);
	BEGIN
	INTEGER COUNT;
	COUNT:=0;
	IF (ROW<1) OR (ROW>8) THEN WRITE("BAD ROW NUMBER")
	ELSE BEGIN
	  FOR I:=1 UNTIL 8 DO
		IF CHECKERBOARD(ROW,I)>0 THEN COUNT:=COUNT+1;
	  WRITE(COUNT," PIECES ON ROW ",ROW)
	 END
	END;

\F2a)
\F1PROCEDURE REDK_ON_COL(INTEGER VALUE COL);
	BEGIN
	INTEGER COUNT;
	COUNT:=0;
	IF (COL<1) OR (COL>8) THEN WRITE("BAD COL NUMBER")
	ELSE BEGIN
	  FOR I:=1 UNTIL 8 DO
		IF CHECKERBOARD(COL,I)=3 THEN COUNT:=COUNT+1;
	  WRITE(COUNT," PIECES ON COL ",COL)
	 END
	END;

\F2b)
\F1PROCEDURE BLACK_ON_DIAG;
	BEGIN
	INTEGER COUNT;
	COUNT:=0;
	FOR I:=1 UNTIL 8 DO
		IF (CHECKERBOARD(I,I)<3) AND (CHECKERBOARD(I,I)>0) THEN
			COUNT:=COUNT+1;
	  WRITE(COUNT," BLACK PIECES ON DIAG")
	 END
	END;


\F2(2)
\F1COMMENT THIS PROCEDURE TAKES A STRING AS AN ARGUMENT AND WRITES THAT
STRING ON ONE LINE WITHOUT ANY BLANKS EXCEPT ONE AT THE START.;
\F0Output for two given procedure calls:
\F1 THISISFULLOFHOLES.
 BENJAMINFRANKLINWOREGREENUNDERWEAR.







\F2(3)
\F0a) what happens if there are no letters in TEXT?
	-the procedure will return a blank
b) what happens if POS is 100?
	-the procedure will return a blank
c) what happens if POS is -4?
	-the computer will quit in disgust when testing \F1(TEXT(POS|1)>="A")
\F0d) if in b) or c) you thought the computer would quit in disgust, outline a change
	so that the procedure would not blow up
	-simply test for POS>=0 and only do the while loop if that is true
e) suppose the following statements came after the procedure in the main program.
	What would they print out? (Here is what they printed.)

\F1T
A
6
M
14
       (this line has one blank written on it)


\F2(4)
\F0\JThis procedure counts the number of alphabetic letters in the string, TEXT,
and prints out the result.
If NEXT_LETTER added one to POS then the WHILE loop could be written as follows:\.
\F1WHILE NEXT_LETTER(TEXT,CHARPOS)¬=" " DO
	COUNT:=COUNT+1;

\F0\JThe while loop works because the procedure NEXT_LETTER always returns a 
blank when it cannot find another letter in the string.\.


\F2(5)
\F1BEGIN
COMMENT THIS PROGRAM READS A STRING AND PRINTS OUT THE SUBSTRING ENCLOSED BY
  < AND >;
STRING(80) TEXT;
INTEGER POS;
READ(TEXT);
POS:=0;
WHILE (POS<80) AND (TEXT(POS|1)¬="<") DO
	POS:=POS+1;
COMMENT NOW WE HAVE FOUND "<" IF THERE IS ONE;
IF POS>78 THEN WRITE("NO < IN STRING.")
ELSE BEGIN
	POS:=POS+1;
	WHILE (POS<80) AND (TEXT(POS|1)¬=">") DO
		BEGIN
		WRITEON(TEXT(POS|1));
		POS:=POS+1
		END;
	IF POS=80 THEN WRITE("NO > IN STRING.")
    END
END.
\F2CS 105 
Outline for lecture 17
30 April 1976


\F0\JWe will discuss text processing, one of the most important uses of computers.
Text processing includes processing of letters, papers, books, etc.  The
processing may include spelling correction, justification, printing of page
numbers, etc.

Putting double quotes around all text to be read in would be a pain when
there is a large amount of text.  Therefore AlgolW provides a READCARD command.
READ and READON try to interpret the punches in a data card as integers, reals,
or strings.  READCARD does not interpret the data card at all, it merely reads
all 80 columns and stores this in a string of length 80.  You could consider
column 0 and column 81 of the card to have implicit quotes if you wish.
READCARD, like READ, takes as many parameters as you want to give it.  Its form
is as follows:\.

\F1READCARD(<list of variable names separated by commas>);

\F0\JEach variable name in the list must be declared STRING(80).  READCARD reads
one card for each variable name in the list.  Below is a program for
lining up the right margin of some text.\.

\F1BEGIN
STRING(80) TEXT;     INTEGER POS;    STRING(30) WORD;
STRING(1) PROCEDURE NEXTCHAR;
COMMENT THIS PROCEDURE ALWAYS GETS THE NEXT CHARACTER FROM THE INPUT AFTER
  DECIDING WHETHER TO READ A NEW CARD OR NOT.  POS POINTS TO THE LAST
  CHARACTER THAT HAS ALREADY BEEN ANALYZED.;
	BEGIN
	IF POS=79 THEN
		BEGIN  POS:=0;  READCARD(TEXT)  END
	ELSE POS:=POS+1;
	TEXT(POS|1)
	END;
STRING(30) PROCEDURE NEXTWORD;
COMMENT THIS PROCEDURE IS LEFT AS AN EXERCISE.  IT USES NEXTCHAR TO KEEP GETTING
  CHARACTERS, IT STORES THE CHARACTERS OF A WORD IN AN ANSWER VARIABLE AND WHEN
  IT HAS A WHOLE WORD IT RETURNS THIS WORD AS ITS VALUE.  A WORD IS DEFINED FOR
  THIS PROBLEM AS ALL THE NON-BLANK SYMBOLS BETWEEN TWO BLANKS.  THIS PROCEDURE
  ALSO SETS THE GLOBAL VARIABLE WORDLENGTH TO THE LENGTH OF THE WORD IT FINDS.;
READ(TEXT);  POS:=-1;  WORD:=NEXTWORD;  OUTPUT_POS:=0;
COMMENT TEXT AND POS ARE INITIALIZED SO THAT NEXTCHAR WILL WORK THE FIRST TIME.
  WORD AND OUTPUT_POS ARE INITIALIZED SO THE WHILE LOOP WILL WORK.  BY DOING
  NEXTWORD AT THE END OF THE WHILE LOOP, WE AVOID PRINTING OUT *** AT THE END.;
COMMENT PROGRAM CONTINUED ON BACK;







WHILE WORD¬="***" DO
	BEGIN
	COMMENT IF WORD FITS ON CURRENT LINE THEN PRINT A BLANK IN FRONT OF IT,
	 OTHERWISE START A NEW LINE AND RESET OUTPUT_POS.;
	IF 100-OUTPUT_POS >= WORDLENGTH+1 THEN WRITEON(" ")
	ELSE BEGIN
		WRITE(" ");
		OUTPUT_POS:=0
	  END;
	FOR CTR:=0 UNTIL WORDLENGTH-1 DO WRITEON(WORD(CTR|1));
	  COMMENT PRINT WORD, THEN UPDATE OUTPUT_POS AND GET NEXT WORD TO PROCESS.;
	OUTPUT_POS:=OUTPUT_POS+WORDLENGTH+1;
	WORD:=NEXTWORD;
	END
END.
\F1CS 105 
Outline for lecture 20
14 May 1976                                                 \f4A


\F3\CUse not vain repetition like the heathens do.


\F0\JRECURSION refers to the technique of defining something in terms of
itself.  A simple mathematical example is the factorial function which
may be defined as follows:\.

\F3Factorial(n)= n*factorial(n-1)  if n>1,  factorial(1)=1.

\F0\JA recursive definition must explicitly define a value for at least
one input, or the definition would be circular.  The basic idea of recursion
is to solve a problem by joining some simple step (like multiplying n
times a number) with the same problem in a slightly simpler environment
(computing factorial(n-1)).  Eventually the environment will be simple enough
so that the solution will be simple (factorial(1)).\.


\F1PROCEDURE HANOI(INTEGER VALUE NUMBER,ORIGIN,TERMINUS,SIDING);
COMMENT THIS PROCEDURE PRINTS OUT THE SOLUTION TO THE TOWER OF HANOI
PROBLEM OF MOVING NUMBER DISCS FROM PEG ORIGIN TO PEG TERMINUS, ASSUMING
THAT ANY DISCS ALREADY ON THE PEGS SIDING OR TERMINUS ARE LARGER THAN ANY
OF THE PEGS ON ORIGIN.;
IF NUMBER ¬= 0 THEN
	BEGIN
	HANOI(NUMBER-1,ORIGIN,SIDING,TERMINUS);
	WRITE("MOVE TOP DISC ON ",ORIGIN," TO ",TERMINUS);
	HANOI(NUMBER-1,SIDING,TERMINUS,ORIGIN)
	END;


\F0\JExtra problem for chess buffs.  In a few lines you can write a program
that will play perfect chess.  It will be recursive but would not make its
first move for millions of years even if it was run on the fastest computer
we know of.  Write the program in English that could be translated sort of
into Algol and assume the following primitives:  a type of variable that
will hold a chess position, a procedure GAMEOVER(CHESS_POSITION) which
returns true if the chess position is at the end of a game else false,
a procedure WINNER(CHESS_POSITION)  which returns BLACK, WHITE, or DRAW
when given a position at the end of a chess game, 
and a procedure LEGALMOVES(CHESS_POSITION)
which returns a list of positions that can be obtained from CHESS_POSITION
by making legal chess moves.  If you are interested in working this problem
and need help, see Dave Wilkins.\.